Computer processes are often subdivided into a variety of functions which may be executed as tasks in serial and/or parallel fashion. These computer processes can be used to gather and act upon information, and to bring about some result in response to the information. These functional task systems find use in a variety of important environments. Examples may include monitor and control of an industrial process, such as a power generation and distribution system, or monitor and control of complex equipment, such as an aircraft or spacecraft.
In real-time systems, such as those mentioned above, execution of tasks can include both periodic tasks and aperiodic tasks. One known way of executing periodic tasks is to use rate monotonic scheduling (RMS). The classical RMS formulation is for strictly periodic task sets. To specify a periodic task set, each of n tasks, say τi, where 1≦i≦n, is associated with a period Ti and a worst case compute time Ci. Each task τi will be dispatched and executed at the rate 1/Ti, and in worst case it will consume processor time equal to Ci at each dispatch. Each task is implicitly assigned a priority which is determined by its rate (or equivalently, the inverse of its period), with priority equal to the ranking of the rate.
The RMS scheduler schedules periodic tasks having hard deadlines. Viable real-time systems must also be capable of executing aperiodic tasks, which can have hard deadlines or soft deadlines. It is desirable for a task scheduling system to schedule a mixture of periodic and aperiodic tasks in such as way that all periodic task deadlines are met and the response times for the aperiodic tasks are as small as possible.
In “An Optimal Algorithm for Scheduling Soft-Aperiodic Tasks in Fixed-Priority Preemptive Systems”, John P. Lehoczky and Sandra Ramos-Thuel, Real-Time Systems Symposium, IEEE Proceedings, December, 1992, there is described a slack-stealing algorithm. This algorithm creates a passive task which, when prompted for service, attempts to make time for servicing aperiodic tasks by “stealing” all the processing time it can from the periodic tasks without causing their deadlines to be missed. This is equivalent to “stealing slack” from the periodic tasks. The slack-stealing algorithm was demonstrated to provide substantial improvements in the response times for aperiodic tasks. In addition, the slack stealing algorithm was described as further improved by cooperating with a reclaiming algorithm that makes available for aperiodic service any processing time unused by the periodic tasks when they require less than their worst-case execution times.
It is known in prior data processing systems to employ time partitioning, wherein time is divided into partitions, and each partition is guaranteed a certain amount of execution time. Time partitioning is useful in encapsulating the effects of timing faults within a time partition. Time fault isolation can significantly reduce system development and maintenance costs, since only tasks within a time partition need to be checked for timing correctness. However, in known time partitioning systems, a disadvantage is that unused processing time in one partition is not made available to tasks in other time partitions, resulting in unused processor capacity.
Thus there is a significant need in the art for a task scheduler that can find slack in a time-partitioned system and make it available to tasks in more than one time partition.